|
In computational geometry and geometric graph theory, a ''β''-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points ''p'' and ''q'' are connected by an edge whenever all the angles ''prq'' are sharper than a threshold determined from the numerical parameter ''β''. ==Circle-based definition== Let ''β'' be a positive real number, and calculate an angle ''θ'' using the formulas : For any two points ''p'' and ''q'' in the plane, let ''R''''pq'' be the set of points for which angle ''prq'' is greater than ''θ''. Then ''R''''pq'' takes the form of a union of two open disks with diameter ''βd''(''p'',''q'') for ''β'' ≥ 1 and ''θ'' ≤ π/2, and it takes the form of the intersection of two open disks with diameter ''d''(''p'',''q'')/''β'' for ''β'' ≤ 1 and ''θ'' ≥ π/2. When ''β'' = 1 the two formulas give the same value ''θ'' = π/2, and ''R''''pq'' takes the form of a single open disk with ''pq'' as its diameter. The ''β''-skeleton of a discrete set ''S'' of points in the plane is the undirected graph that connects two points ''p'' and ''q'' with an edge ''pq'' whenever ''R''''pq'' contains no points of ''S''. That is, the ''β''-skeleton is the empty region graph defined by the regions ''R''''pq''.〔.〕 When ''S'' contains a point ''r'' for which angle ''prq'' is greater than ''θ'', then ''pq'' is not an edge of the ''β''-skeleton; the ''β''-skeleton consists of those pairs ''pq'' for which no such point ''r'' exists. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「beta skeleton」の詳細全文を読む スポンサード リンク
|